home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / glimpse-2.1 / agrep / follow.c < prev    next >
C/C++ Source or Header  |  1995-05-16  |  5KB  |  255 lines
  1. /* Copyright (c) 1994 Sun Wu, Udi Manber, Burra Gopal.  All Rights Reserved. */
  2. /* the functions in this file take a syntax tree for a regular
  3.    expression and produce a DFA using the McNaughton-Yamada
  4.    construction.                        */
  5.  
  6. #include <stdio.h>
  7. #include <string.h>
  8. #include <stdlib.h>
  9. #include <unistd.h>
  10. #include "re.h"
  11.  
  12. #define TRUE    1
  13.  
  14. extern Pset pset_union(); 
  15. extern int pos_cnt;
  16. extern Re_node parse();
  17.  
  18. Re_lit_array lpos; 
  19.  
  20.  
  21. /*  extend_re() extends the RE by adding a ".*(" at the front and a "("
  22.     at the back.                               */
  23.  
  24. char *extend_re(s)
  25. char *s;
  26. {
  27.     char *s1;
  28.  
  29.     s1 = malloc((unsigned) strlen(s)+4+1);
  30.     return strcat(strcat(strcpy(s1, ".*("), s), ")");
  31. }
  32.  
  33. void free_pos(fpos, pos_cnt)
  34. Pset_array fpos;
  35. int pos_cnt;
  36. {
  37.     Pset tpos, pos;
  38.     int i;
  39.  
  40.     if ((fpos == NULL) || (*fpos == NULL)) return;
  41.     for (i=0; i<pos_cnt; i++) {
  42.         pos = (*fpos)[i];
  43.         while (pos != NULL) {
  44.             tpos = pos;
  45.             pos = pos->nextpos;
  46.             free(tpos);
  47.         }
  48.     }
  49.     free(fpos);
  50. }
  51.  
  52. /* Function to clear out a Ch_Set */
  53. void free_cset(cset)
  54. Ch_Set cset;
  55. {
  56.     Ch_Set tset;
  57.  
  58.     while (cset != NULL) {
  59.         tset = cset;
  60.         cset = cset->rest;
  61.         free(tset->elt);
  62.         free(tset);
  63.     }
  64. }
  65.  
  66. /* Function to clear out the tree of re-nodes */
  67. void free_re(e)
  68. Re_node e;
  69. {
  70.     Pset tpos, pos;
  71.     int tofree = 0;
  72.  
  73.     if (e == NULL) return;
  74.  
  75. /*
  76.  * Was creating "reading freed memory", "freeing unallocated/freed memory"
  77.  * errors. So abandoned it. Leaks are now up by 60B/call to 80B/call
  78.  * -bg
  79.  *
  80.     if ((Lastpos(e)) != (Firstpos(e))) tofree = 1;
  81.     pos = Lastpos(e);
  82.     while (pos != NULL) {
  83.         tpos = pos;
  84.         pos = pos->nextpos;
  85.         free(tpos);
  86.     }
  87.     Lastpos(e) = NULL;
  88.  
  89.     if (tofree) {
  90.         pos = Firstpos(e);
  91.         while (pos != NULL) {
  92.             tpos = pos;
  93.             pos = pos->nextpos;
  94.             free(tpos);
  95.         }
  96.         Firstpos(e) = NULL;
  97.     }
  98. */
  99.  
  100.     switch (Op(e)) {
  101.     case EOS:
  102.         if (lit_type(Lit(e)) == C_SET) free_cset(lit_cset(Lit(e)));
  103.         free(Lit(e));
  104.         break;
  105.     case OPSTAR:
  106.         free_re(Child(e));
  107.         break;
  108.     case OPCAT:
  109.         free_re(Lchild(e));
  110.         free_re(Rchild(e));
  111.         break;
  112.     case OPOPT:
  113.         free_re(Child(e));
  114.         break;
  115.     case OPALT:
  116.         free_re(Lchild(e));
  117.         free_re(Rchild(e));
  118.         break;
  119.     case LITERAL:
  120.         if (lit_type(Lit(e)) == C_SET) free_cset(lit_cset(Lit(e)));
  121.         free(Lit(e));
  122.         break;
  123.     default: 
  124.         fprintf(stderr, "free_re: unknown node type %d\n", Op(e));
  125.     }
  126.     free(e);
  127.     return;
  128. }
  129.  
  130.  
  131. /* mk_followpos() takes a syntax tree for a regular expression and
  132.    traverses it once, computing the followpos function at each node
  133.    and returns a pointer to an array whose ith element is a pointer
  134.    to a list of position nodes, representing the positions in
  135.    followpos(i).                            */
  136.  
  137. void mk_followpos_1(e, fpos)
  138. Re_node e;
  139. Pset_array fpos;
  140. {
  141.     Pset pos;
  142.     int i;
  143.  
  144.     switch (Op(e)) {
  145.     case EOS: 
  146.         break;
  147.     case OPSTAR:
  148.         pos = Lastpos(e);
  149.         while (pos != NULL) {
  150.             i = pos->posnum;
  151.             (*fpos)[i] = pset_union(Firstpos(e), (*fpos)[i]);
  152.             pos = pos->nextpos;
  153.         }
  154.         mk_followpos_1(Child(e), fpos);
  155.         break;
  156.     case OPCAT:
  157.         pos = Lastpos(Lchild(e));
  158.         while (pos != NULL) {
  159.             i = pos->posnum;
  160.             (*fpos)[i] = pset_union(Firstpos(Rchild(e)), (*fpos)[i]);
  161.             pos = pos->nextpos;
  162.         }
  163.         mk_followpos_1(Lchild(e), fpos);
  164.         mk_followpos_1(Rchild(e), fpos);
  165.         break;
  166.     case OPOPT:
  167.         mk_followpos_1(Child(e), fpos);
  168.         break;
  169.     case OPALT:
  170.         mk_followpos_1(Lchild(e), fpos);
  171.         mk_followpos_1(Rchild(e), fpos);
  172.         break;
  173.     case LITERAL:
  174.         break;
  175.     default: 
  176.         fprintf(stderr, "mk_followpos: unknown node type %d\n", Op(e));
  177.     }
  178.     return;
  179. }
  180.  
  181. Pset_array mk_followpos(tree, npos)
  182. Re_node tree;
  183. int npos;
  184. {
  185.     int i;
  186.     Pset_array fpos;
  187.  
  188.     if (tree == NULL || npos < 0) return NULL;
  189.     fpos = (Pset_array) malloc((unsigned) (npos+1)*sizeof(Pset));
  190.     if (fpos == NULL) return NULL;
  191.     for (i = 0; i <= npos; i++) (*fpos)[i] = NULL;
  192.     mk_followpos_1(tree, fpos);
  193.     return fpos;
  194. }
  195.  
  196. /* mk_poslist() sets a static array whose i_th element is a pointer to
  197.    the RE-literal at position i.  It returns 1 if everything is OK,  0
  198.    otherwise.                                */
  199.  
  200. /* init performs initialization actions; it returns -1 in case of error,
  201.    0 if everything goes OK.                        */
  202.  
  203. int init(s, table)
  204. char *s; 
  205. int table[32][32];
  206. {
  207.     Pset_array fpos;
  208.     Re_node e;
  209.     Pset l;
  210.     int i, j;
  211.     char *s1;
  212.  
  213.     if ((s1 = extend_re(s)) == NULL) return -1;
  214.     if ((e = parse(s1)) == NULL) {
  215.         free(s1);
  216.         return -1;
  217.     }
  218.     free(s1);
  219.     if ((fpos = mk_followpos(e, pos_cnt)) == NULL) {
  220.         free_re(e);
  221.         return -1;
  222.     }
  223.     for (i = 0; i <= pos_cnt; i += 1) {
  224. #ifdef Debug
  225.         printf("followpos[%d] = ", i);
  226. #endif
  227.         l = (*fpos)[i];
  228.         j = 0;
  229.         for ( ; l != NULL; l = l->nextpos)  {
  230. #ifdef Debug
  231.             printf("%d ", l->posnum);
  232. #endif
  233.             table[i][j] = l->posnum;
  234.             j++;
  235.         } 
  236. #ifdef Debug
  237.         printf("\n");
  238. #endif
  239.     }
  240. #ifdef Debug
  241.     for (i=0; i <= pos_cnt; i += 1)  {
  242.         j = 0;
  243.         while (table[i][j] != 0) {
  244.             printf(" %d ", table[i][j]);
  245.             j++;
  246.         }
  247.         printf("\n");
  248.     }
  249. #endif
  250.     free_pos(fpos, pos_cnt);
  251.     free_re(e);
  252.     return (pos_cnt);
  253. }
  254.  
  255.